package com.mingqi.hw.test91100;

/** 【招聘】
 * 某公司组织一场公开招聘活动，假设由于人数和场地的限制，每人每次面试的时长不等，并已经安排给定，用(S1,E1)、(S2,E2)、(Sj,Ej)…(Si < Ei，均为非负整数)表示每场面试的开始和结束时间。面试采用一对一的方式，即一名面试官同时只能面试一名应试者，一名面试官完成一次面试后可以立即进行下一场面试，且每个面试官的面试人次不超过m。
 * 为了支撑招聘活动高效顺利进行，请你计算至少需要多少名面试官。
 * 输入描述:
 * 输入的第一行为面试官的最多面试人次m，第二行为当天总的面试场次n，接下来的n行为每场面试的起始时间和结束时间，起始时间和结束时间用空格分隔。
 * 其中，1 <= n, m <= 500
 * 输出描述:
 * 输出一个整数，表示至少需要的面试官数量。
 * 示例1
 * 输入
 * 2
 * 5
 * 1 2
 * 2 3
 * 3 4
 * 4 5
 * 5 6
 * 输出
 * 3
 * 说明
 * 总共有5场面试，且面试时间都不重叠，但每个面试官最多只能面试2人次，所以需要3名面试官。
 * 示例2
 * 输入
 * 3
 * 3
 * 1 2
 * 2 3
 * 3 4
 * 输出
 * 1
 * 说明
 * 总共有3场面试，面试时间都不重叠，每个面试官最多能面试3人次，所以只需要1名面试官。
 * 示例3
 * 输入
 * 3
 * 3
 * 8 35
 * 5 10
 * 1 3
 * 输出
 * 2
 * 说明
 * 总共有3场面试，[5,10]和[8,35]有重叠，所以至少需要2名面试官。
 *
 * 初始化一个最小堆，堆中的元素是结束时间最早且未被分配的面试。
 * 初始化一个计数器，表示当前需要的面试官数量。
 * 遍历所有的面试，对于每个面试：
 * 如果堆为空（即没有正在进行的面试）或者堆顶的面试已经结束（即堆顶元素的结束时间小于等于当前面试的开始时间），则当前面试可以由堆顶的面试官进行，更新堆顶的面试结束时间为当前面试的结束时间，并将堆顶元素重新放回堆中。
 * 如果堆不为空且堆顶的面试还在进行中（即堆顶元素的结束时间大于当前面试的开始时间），则需要新增一个面试官来进行当前面试，将当前面试的结束时间放入堆中。
 * 无论哪种情况，都需要检查当前面试官的面试次数是否超过了限制m，如果超过了，则需要新增一个面试官。
 * 遍历完成后，堆中剩余的面试都需要额外的面试官来完成，因此面试官的数量需要加上堆的大小。
 */
import java.util.PriorityQueue;
import java.util.Scanner;

public class ZT96 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt(); // 面试官最多面试人次
        int n = scanner.nextInt(); // 面试场次

        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]); // 最小堆，按照结束时间排序
        int interviewerCount = 0; // 面试官数量

        for (int i = 0; i < n; i++) {
            int start = scanner.nextInt();
            int end = scanner.nextInt();
            int[] interview = {start, end};

            // 如果堆为空或者堆顶的面试已经结束
            if (pq.isEmpty() || pq.peek()[1] <= start) {
                pq.offer(interview);
            } else {
                // 需要新增面试官
                pq.offer(interview);
                interviewerCount++;

                // 如果当前面试官的面试次数超过限制，需要新增面试官
                while (!pq.isEmpty() && pq.peek()[1] <= interview[1] && interviewerCount >= m) {
                    pq.poll();
                    interviewerCount--;
                }
            }

            // 如果当前面试官的面试次数达到限制，需要新增面试官
            if (interviewerCount >= m) {
                interviewerCount++;
            }
        }

        // 堆中剩余的面试需要额外的面试官
        interviewerCount += pq.size();

        System.out.println(interviewerCount);
        scanner.close();
    }
}
